Multiprocessing is a mode of operation in which two or more processing units each carry out one or more processes (programs or sets of instructions) in tandem. The objective of a multiprocessing system is to increase processing speed. Typically, this is accomplished by each processing unit operating on a different set of instructions or on different threads of the same process. A process may execute one or more threads. Each thread has it own processor context, including its own program context. Traditionally, for an application to take advantage of the benefits of multiprocessing, a software developer must write the application to be multithreaded. As used herein, a multithreaded application refers to a program capable of running two or more threads simultaneously.
On a multiprocessor or multi-core system (collectively referred to herein as a “multiprocessing system”), two or more of the threads of a multithreaded application may be able to execute at the same time, with each processor or core running a particular thread. It is common for threads of a multithreaded application to share resources during concurrent execution, such as, for example, memory. As used herein, concurrent execution refers to the simultaneous execution of two or more threads of a multithreaded application. A consequence of concurrent execution is that two or more threads of a multithreaded application may read and/or update the same shared resource. For example, one thread may modify a value of a shared memory location while another thread executes a sequence of operations that depend on the value stored in the shared memory location.
Under the traditional software development model, software developers spend a substantial amount of time identifying and attempting to correctly synchronize parallel threads within their multithreaded applications. For example, a developer may explicitly use locks, semaphores, barriers, or other synchronization mechanisms to control access to a shared resource. When a thread accesses the shared resource, the synchronization mechanism prevents other threads from accessing the resource by suspending those threads until the resource becomes available. Software developers who explicitly implement synchronization mechanisms also typically spend a substantial amount of time debugging their synchronization code. However, software defects (referred to as “bugs”) resulting from synchronization errors typically manifest themselves transiently (i.e., a bug may appear only on a particular sequence or sequences of interleaved thread operations). As a result, defective software might execute correctly hundreds of times before a subtle synchronization bug appears.
It is difficult to develop software for multiprocessing systems because of the nondeterministic behavior created by the various interleaving of threads on such systems. An interleaving refers to an order of thread operations that may include interaction between threads. The number of possible interleavings between threads significantly increases as the number of threads increase. Consequently, multithreaded applications present additional challenges in terms of error detection and modeling program behavior. For example, given the same input to a multithreaded application, a multiprocessing system will interleave thread operations nondeterministically, thereby producing different output each time the multithreaded application is executed. FIG. 1 is a high-level diagram showing an example of two possible thread interleavings in a multithreaded application executed on a multiprocessing system. As illustrated, the application includes at least two threads: thread 1 and thread 2. When the application is invoked, at some point in time, thread 1 executes an operation settings the value of variable A to one (A=1) followed by an operation settings the value of variable B to the value of variable A (B=A), and thread 2 executes an operation settings the value of variable B to zero (B=0) followed by an operation settings the value of variable A to the value of variable B (A=B). As illustrated, the operations of thread 1 and thread 2 are interleaved nondeterministically, thereby producing different output each time the application is invoked. That is, during the first illustrated invocation, the interleaving of operations resulted in variables A and B each being set to zero, while during the second illustrated invocation, the interleaving of operations resulted in variables A and B each being set to one.
Non-determinism in multithreaded execution may arise from small changes in the execution environment, such as, for example, other processes executing simultaneously, differences in the operating system resource allocation, the state of caches, translation lookaside buffers (“TLBs”), buses, interrupts, and other microarchitectural structures. As a result, developing a multithreaded application is significantly more difficult than developing a single-threaded application.
Conventionally, efforts in addressing this problem have focused on deterministically replaying multithreaded execution based on a previously generated log file. However, deterministic replay systems suffer substantial performance degradation as a result of the overhead associated with maintaining the replay log file. Moreover, with deterministic replay, a software developer does not have control over how the interleaving of threads is performed. As a result, synchronization bugs resulting from particular interleavings of operations may not be identified (and, more importantly, corrected) before the software is deployed to a customer. Non-determinism further complicates the software development process in that non-determinism makes it hard to assess test coverage. Good coverage requires both a wide range of program inputs and a wide range of possible thread interleavings.